package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         41,
		Discription: "缺失的第一个正整数",
		Level:       3,
		Labels: map[string]int{
			"哈希表":  1,
			"空间复用": 1,
		},
	})
}

//O(3n)，把原始数组当哈希表，用值当映射的key
func FirstMissingPositive(nums []int) int {
	for index, val := range nums {
		//小于等于0的元素和大于等于数组长度的元素不需要考虑  val >=1  && val <= len(nums)
		//如果要换的位置已经满足值和下标的关系了，不需要换 nums[val-1] != val
		//本身位置就满足值和下标的关系了，不需要换 val != index+1
		for val >= 1 && val <= len(nums) && val != index+1 && nums[val-1] != val {
			nums[val-1], nums[index] = nums[index], nums[val-1]
			val = nums[index]
		}
	}

	//再次遍历查找第一个值不符合下标的元素，需要O(n)
	for index := range nums {
		if nums[index] != index+1 {
			return index + 1
		}
	}

	//全部满足的情况
	return len(nums) + 1
}
